package cn.edu.jxau.test;

import java.util.Objects;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * @author Fudashi
 */
public class Main {

	public static void main(String[] args) {

		Integer[] preOrder = new Integer[] { 1, 2, 4, 7, 3, 5, 6, 8 };
		Integer[] inOrder = new Integer[] { 4, 7, 2, 1, 5, 3, 8, 6 };
		BinaryTree<Integer> tree = new BinaryTree<Integer>(preOrder, inOrder);
		tree.preOrder();
		System.out.println();
		tree.inOrder();
	}

}

class BinaryTree<T> {

	private Node root;

	public BinaryTree(T[] preOrder, T[] inOrder) {

		Objects.requireNonNull(preOrder, "参数preOrder不能为空");
		if (preOrder.length == 0) {
			return;
		}
		Objects.requireNonNull(inOrder, "参数inOrder不能为空");
		if (inOrder.length == 0) {
			return;
		}
		if (preOrder.length != inOrder.length) {
			throw new IllegalArgumentException("preOrder,inOrder长度不同无法构造二叉树");
		}
		root = construct(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
	}

	private Node construct(T[] preOrder, int preStart, int preEnd, T[] inOrder, int inStart, int inEnd) {

		System.out.printf("preStart=%d,preEnd=%d,inStart=%d,inEnd=%d\n", preStart, preEnd, inStart, inEnd);
		Node node = new Node(preOrder[preStart]);
		if (preStart == preEnd) {
			if (inStart == inEnd) {
				if (preOrder[preStart].equals(inOrder[inStart])) {
					return node;
				}
			} else {
				throw new RuntimeException("无效的序列");
			}
		}
		int i = inStart;
		for (; i <= inEnd; i++) {
			if (node.data.equals(inOrder[i])) {
				break;
			}
		}
		if (i > inEnd) {
			throw new RuntimeException("无效的序列");
		}
		int leftLen = i - inStart; // 1
		int rightLen = inEnd - i; // 2
		if (leftLen > 0) {
			node.left = construct(preOrder, preStart + 1, preStart + leftLen, inOrder, inStart, inStart + leftLen - 1);
		}
		if (rightLen > 0) {
			node.right = construct(preOrder, preStart + leftLen + 1, preEnd, inOrder, i + 1, i + rightLen);
		}
		return node;

	}

	public void preOrder() {
		preOrder(root);
	}

	private void preOrder(Node node) {

		if(node == null) {
			return ;
		}
		System.out.print(node.data + "\t");
		preOrder(node.left);
		preOrder(node.right);
	}

	public void inOrder() {
		inOrder(root);
	}

	private void inOrder(Node node) {
		
		if(node == null) {
			return ;
		}
		inOrder(node.left);
		System.out.print(node.data + "\t");
		inOrder(node.right);
	}

	private class Node {
		private T data;
		private Node left;
		private Node right;

		public Node(T data) {
			this.data = data;
		}
	}
}